BOJ_1863_스카이라인 쉬운거

처음에는 list와 if문으로 풀었는데 Stack활용이 가능할 것 같아서 코드를 변경했다

1. list - if
   높이를 순서대로 확인하면서 직전보다 높이가 낮다/높다/같다로 경우를 나눠 처리한다
   현재 높이가 높다면 - 새로운 건물이 등장한 것이므로 개수를 세고 list에 넣는다
   높이가 같다면 - 넘어간다
   높이가 낮다면 - list를 돌면서 1) 현재 높이보다 높은 것이 있다면 현재 높이로 인하여 이어질 수 없으므로 탐색이 끝난 건물이기 떄문에 remove한다 2) 현재 높이와 같은 것이 있다면 개수를 세지 않고 list에 추가하지도 않는다

   2. Stack
      list를 사용한 이유는 리스트에 담겨 있는 모든 높이를 탐색해야 한다고 생각했기 때문이다
      하지만 조건이 1과 같다면 모든 원소를 탐색할 필요 없다 왜냐하면
   1. 만약 peek() 한 원소가 현재 높이보다 높다면 pop() 해서 삭제하고 그 다음 원소를 탐색한다
   2. 만약 peek() 한 원소가 현재 높이보다 작거나 같다면 원소의 앞은 처음부터 더 높은 것이 없었거나, 조건에 따라 삭제되어 높은 것이 남아있지 않거나 한 경우만 존재하기에 peek() 한 원소보다 높은 것이 없다. 따라서 현재 원소가 이 앞을 탐색해야 할 필요가 없다!

불필요한 탐색을 하지 않기 때문에 2번의 방법이 더 효율적이다

package BJO;  
  
import java.util.Scanner;  
import java.util.Stack;  
  
public class BJO_1863_스카이라인쉬운거 {  
  
    public static void main(String[] args) {  
       Scanner scan = new Scanner(System.in);  
  
       int n = scan.nextInt();  
       int[][] arr = new int[n][2];  
       for (int i = 0; i < n; i++) {  
          arr[i][0] = scan.nextInt();  
          arr[i][1] = scan.nextInt();  
       }  
  
       int cnt = 0;  
       Stack<Integer> stack = new Stack<>();  
  
       if (arr[0][1] > 0) {  
          stack.push(arr[0][1]);  
          cnt++;  
       }  
  
       for (int i = 1; i < n; i++) {  
          // 내가 더 크네  
          if (arr[i][1] > arr[i - 1][1]) {  
             stack.push(arr[i][1]);  
             cnt++;  
          }  
  
          // 내가 더 작네  
          else if (arr[i][1] < arr[i - 1][1]) {  
             boolean check = false;  
  
             while (!stack.isEmpty()) {  
                if (arr[i][1] >= stack.peek()) {  
                   if (arr[i][1] == stack.peek()) {  
                      check = true;  
                   }  
                   break;  
                } else {  
                   stack.pop();  
                }  
             }  
  
             // 같은 높이 애가 없다  
             if (!check && arr[i][1] > 0) {  
                stack.push(arr[i][1]);  
                cnt++;  
             }  
          }  
            
          // 같은 높이는 무시하고 넘어감  
       }  
  
       System.out.println(cnt);  
    }  
}

#stack